1925E - Space Harbour - CodeForces Solution

#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define pb push_back
#define B break
#define C continue
#define R return
#define mid ((l+r)/2)
#define left (2*idx)
#define right (2*idx+1)

using namespace std;

const ll Mod=1e9+7 , N = 500500 , inf=1e18;
ll n , m , k , q , x , y , z , a[N] , tree[N<<2] , ans=0 , sum=0 , mn=inf , mx=0 ;
pair<ll,ll>lazy[N<<2];
pair<ll,ll>b[N];

ll getlr(ll x,ll l,ll r){
    ll ri = x-l , le = x-r;
    ll res = ri*(ri+1)/2;
    res -= (le*(le-1))/2;
    return res;
}

void push_lazy(int idx,int l,int r){
    if(lazy[idx].F){
        tree[idx] = lazy[idx].F*(getlr(lazy[idx].S,l,r));
        if(l!=r){
            lazy[left] = lazy[idx];
            lazy[right] = lazy[idx];
        }
        lazy[idx]={0,0};
    }
}

void mrg(int idx){
    tree[idx]=tree[left]+tree[right];
}

void update(int i,int j,int id,ll val,int l=1,int r=n,int idx=1){
    push_lazy(idx,l,r);
    if(l>j || r<i)return;
    if(l>=i && r<=j){
        lazy[idx] = {val,id};
        push_lazy(idx,l,r);
        return ;
    }
    update(i,j,id,val,l,mid,left);
    update(i,j,id,val,mid+1,r,right);
    mrg(idx);
}

ll query(int i,int j,int l=1,int r=n,int idx=1){
    push_lazy(idx,l,r);
    if(l>j || r<i)return 0;
    if(l>=i && r<=j)return tree[idx];
    return query(i,j,l,mid,left)+query(i,j,mid+1,r,right);
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m >> q ;
    int prev=1;
    ll val=0;
    set<int>s;
    for(int i=1 ; i<=m ; i++){
        cin >> b[i].F ;
    }
    for(int i=1 ; i<=m ; i++){
        cin >> b[i].S;
    }
    sort(b+1,b+1+m);
    for(int i=1 ; i<=m ; i++){
        x=b[i].F;
        y=b[i].S;
        a[x]=y;
        s.insert(x);
        if(i>1){
            update(prev+1,x,x,val);
        }
        prev=x;
        val=y;
    }
    while(q--){
        cin >> x ;
        if(x==1){
            cin >> x >> y ;
            a[x]=y;
            auto it = s.lower_bound(x);
            update(x+1,*it,*it,y);
            it--;
            update(*it+1,x,x,a[*it]);
            s.insert(x);
        }
        else{
            cin >> x >> y ;
            cout << query(x,y) << '\n';
        }
    }
    return 0;
}